#include <cmath>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>

struct TreeNode {
    char val;
    TreeNode *left{nullptr};
    TreeNode *right{nullptr};

    TreeNode(const char &_name) : val(_name), left(nullptr), right(nullptr) {}
};

void destroyTree(TreeNode *root) {
    if (root) {
        destroyTree(root->left);
        destroyTree(root->right);
        delete root;
    }
}

const std::string preRootTraversal(TreeNode *root) {
    if (root == nullptr) {
        return "";
    }
    std::stringstream ss;
    ss << root->val;

    if (root->left) {
        ss << preRootTraversal(root->left);
    }
    if (root->right) {
        ss << preRootTraversal(root->right);
    }

    return ss.str();
}

const std::string midRootTraversal(TreeNode *root) {
    if (root == nullptr) {
        return "";
    }
    std::stringstream ss;

    if (root->left) {
        ss << midRootTraversal(root->left);
    }
    ss << root->val;
    if (root->right) {
        ss << midRootTraversal(root->right);
    }

    return ss.str();
}

const std::string lastRootTraversal(TreeNode *root) {
    if (root == nullptr) {
        return "";
    }
    std::stringstream ss;

    if (root->left) {
        ss << lastRootTraversal(root->left);
    }
    if (root->right) {
        ss << lastRootTraversal(root->right);
    }
    ss << root->val;

    return ss.str();
}

template <typename E>
std::vector<E> vectorAdd(const std::vector<E> &vec1, const std::vector<E> &vec2,
                         const std::vector<E> &vec3) {
    std::vector<E> res;
    res.resize(vec1.size() + vec2.size() + vec3.size());
    int idx = 0;
    for (auto it = vec1.begin(); it != vec1.end(); ++it) {
        res[idx++] = (*it);
    }
    for (auto it = vec2.begin(); it != vec2.end(); ++it) {
        res[idx++] = (*it);
    }
    for (auto it = vec3.begin(); it != vec3.end(); ++it) {
        res[idx++] = (*it);
    }
    return res;
}

const std::vector<std::tuple<int, char>> preLeftView(TreeNode *root,
                                                     int level) {
    std::vector<std::tuple<int, char>> result;
    if (root == nullptr) {
        return result;
    }
    result.push_back(std::make_tuple(level, root->val));
    auto left = preLeftView(root->left, level + 1);
    auto right = preLeftView(root->right, level + 1);
    return vectorAdd(result, left, right);
}

const std::string leftView(TreeNode *root) {
    auto result = preLeftView(root, 0);
    std::stringstream ss;
    int cur_level = -1;
    for (auto [level, val] : result) {
        if (level > cur_level) {
            cur_level = level;
            ss << val;
        }
    }

    return ss.str();
}

const std::vector<std::tuple<int, char>> preRightView(TreeNode *root,
                                                      int level) {
    std::vector<std::tuple<int, char>> result;
    if (root == nullptr) {
        return result;
    }
    result.push_back(std::make_tuple(level, root->val));
    auto right = preRightView(root->right, level + 1);
    auto left = preRightView(root->left, level + 1);
    return vectorAdd(result, right, left);
}

const std::string rightView(TreeNode *root) {
    auto result = preRightView(root, 0);
    std::stringstream ss;
    int cur_level = -1;
    for (auto [level, val] : result) {
        if (level > cur_level) {
            cur_level = level;
            ss << val;
        }
    }

    return ss.str();
}

int main(int agrv, char **argc) {
    TreeNode *root = new TreeNode('A');
    root->left = new TreeNode('B');
    root->right = new TreeNode('G');
    root->left->left = new TreeNode('C');
    root->left->right = new TreeNode('D');
    root->right->right = new TreeNode('H');
    root->left->right->left = new TreeNode('E');
    root->left->right->right = new TreeNode('F');

    std::cout << "先根遍历：" << preRootTraversal(root) << std::endl;
    std::cout << "中根遍历：" << midRootTraversal(root) << std::endl;
    std::cout << "后根遍历：" << lastRootTraversal(root) << std::endl;
    std::cout << "左视图：" << leftView(root) << std::endl;
    std::cout << "右视图：" << rightView(root) << std::endl;
    destroyTree(root);
    return 0;
}
